1. Field of Invention
This invention relates to data storage systems.
2. Related Art
Many computer applications need to store and retrieve information. Information can be stored on hard disks, floppy disks, CD-ROMs, semiconductor RAM memory and similar storage devices. Many of these storage systems are susceptible to data loss of various forms including disk failures. A solution to the problem of disk failure involves use of a RAID (redundant array of independent disks) system. RAID systems use multiple hard drives and space to store parity data generated from the data drives, either on a separate drive (known as the parity disk) or spread out among the multiple drives. The use of multiple hard drives makes it possible to replace faulty hard drives without going off-line; data contained on a drive can be rebuilt using the other data disks and the parity data. If a hard drive fails, a new hard drive can be inserted which the system is running by xe2x80x9chot-swappingxe2x80x9d while on-line. The RAID can rebuild the data on the new disk using the other data disks and the parity data. The performance of a RAID system is improved by disk striping, which interleaves bytes or groups of bytes across multiple drives, so more than one disk is reading and writing simultaneously.
Another problem with storage devices is that they are susceptible to data corruption of various forms, including bit miswrites. While RAID allows a user to determine, using parity data, that there has been corruption of some data included in a stripe, the parity data does not include enough information to restore the corrupted data. More specifically, parity data does not allow a user to determine which data in the stripe has been corrupted; thus we do not know which data is trustworthy.
Checksums are another form of redundant data that can be written to individual disks. The combination of parity bits across the disks and checksums within each disk includes enough information, that the corrupted data can be restored in RAID and other redundant systems.
A second known problem is that disk drives in earlier data detection systems are formatted in a manner incompatible with a standard checksum system. More specifically, the disk drives do not have any space available to store checksum information.
A third known problem is that the prior art of storing checksums does not provide for recovery of lost writes, including writes that did not make it to a disk drive. In such systems, updates to the data and to the checksum occur in one I/O. Recovery in such systems may be incomplete if that particular I/O becomes xe2x80x9clostxe2x80x9d.
Accordingly, it would be advantageous to provide an improved technique for the error checking and correction of data storage systems. This is achieved in an embodiment of the invention that is not subject to the drawbacks of the related art.
The invention provides an improved method and apparatus for a data storage system to be upgraded dynamically including multiple stages to provide redundant data for error checking without needing to take the system off-line.
In a first aspect of the invention, the data storage system is a RAID system composed of multiple hard disk drives and a controller for the drives. Additional redundant data (including data known as checksums) need to be stored on a formatted system that is in use (e.g. xe2x80x9con-linexe2x80x9d). In a preferred embodiment including a set of consecutive blocks on the same disk, numbers 0-63, checksums are computed from the data in blocks 0-62 and placed in block 63. Similar to parity bits, checksums do not provide adequate information on their own because they are limited to detecting errors. The combination of (1) parity bits across the RAID system stored on the parity disk, (2) the remaining uncorrupted data in the data disks and (3) checksums within each disk includes sufficient information so as to enable restoration of corrupt data in RAID systems and other similar devices.
In a second aspect of the invention, a data storage system can be upgraded by following a step-wise procedure that involves reserving permanent checksum blocks and writing the checksums to the checksum blocks. The checksums are placed in permanently reserved checksum block locations after first moving data already in the reserved blocks to unoccupied and unreserved data storage blocks.
In a third aspect of the invention, the checksum block includes a collection of checksums. In a preferred embodiment, this checksum block is one of a set of 64 blocks (0-63) that form a megablock. There are 63 data blocks and 1 checksum block in a megablock. The checksums come in the following form: block checksums (8 byte ID and 4 Adler bytes from the location and data of the block 4K bytes ) and checksum blocks (a collection of 64 of these block checksums). The 64th block checksum in the checksum block checks the checksum block itself. In other embodiments, other formats of data and algorithms other than Adler""s can be used.
In a fourth aspect of the invention, new data is written to data blocks in the previously upgraded system. New checksums are computed and written to new checksum blocks that are separate from the data blocks. Corrupted data can be identified on a particular disk drive in a RAID and other redundant data storage systems and restored using the other data disks and the parity disk while the system is on-line.
In a fifth aspect of the invention, data and checksums are stored in separate blocks. Two separate I/Os are performed (one I/O to updated the data and the second to updated the checksum). This separation allows recovery of information if data fails to be written to a disk or is otherwise xe2x80x9clostxe2x80x9d.
In a preferred embodiment, the invention is operative on a RAID system for a file server. However, in other embodiments, the invention is applicable to any computer data storage system such as a database system or a store and forward system such as cache or RAM.